GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Quickselect</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Quickselect</span></h1>

</header>

</div>

<p><b>Quickselect</b> (<a href="Englisch" class="mw-redirect" title="Englisch">englisch</a> <i>quick</i>, deutsch ‚schnell‘ und <i>to select</i> ‚auswählen‘) ist ein Auswahlverfahren aus der <a href="Informatik" title="Informatik">Informatik</a>, um das k-kleinste Element in einer ungeordneten Liste zu finden. Es bezieht sich auf den <a href="Quicksort" title="Quicksort">Quicksort</a>-<a href="Sortieralgorithmus" class="mw-redirect" title="Sortieralgorithmus">Sortieralgorithmus</a>. Wie Quicksort wurde es von <a href="Tony_Hoare" title="Tony Hoare">Tony Hoare</a> entwickelt und ist daher auch als <i>Hoare-Auswahlalgorithmus</i> bekannt.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Wie Quicksort ist es in der Praxis effizient und hat einen guten <a href="Worst_Case" title="Worst Case">Average Case</a>, jedoch auch eine schlechte Leistung im <a href="Worst_Case" title="Worst Case">Worst Case</a>. Quickselect und seine Varianten sind die am häufigsten verwendeten Selektionsalgorithmen in effizienten Implementierungen in der Praxis.

</p><p>Quickselect verwendet den gleichen Gesamtansatz wie Quicksort, wählt ein Element als <a href="Pivotelement" title="Pivotelement">Pivot</a> und teilt die Daten in zwei Teile, basierend auf dem Pivot, entsprechend kleiner oder größer als der Pivot. Anstatt jedoch, wie bei Quicksort, in beide Seiten zurückzukehren, kehrt die Schnellauswahl nur in eine Seite zurück – die Seite mit dem gesuchten Element. Dies reduziert die durchschnittliche Komplexität von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log(n))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75ac2d2b1318fe271226ab13f0eb6c0129df930f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.617ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log(n))}" loading="lazy"></span> auf <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span>, mit einem Worst Case von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></span>.

</p><p>Wie bei Quicksort ist die Schnellauswahl im Allgemeinen als <a href="In-place" class="mw-redirect" title="In-place">In-Place-Algorithmus</a> implementiert, und über die Auswahl des k'ten Elements hinaus sortiert sie die Daten teilweise auch.

</p>

<div class="mw-heading mw-heading2"><h2 id="Prinzip">Prinzip</h2></div>

<p>In Quicksort gibt es eine Unterprozedur namens partition, die in linearer Zeit eine Liste (von links nach rechts) in zwei Teile gruppieren kann: diejenigen, die kleiner als ein bestimmtes Element sind, und solche, die größer als oder gleich dem Element sind. Hier ist Pseudocode, der eine Partition über die Elementliste[pivotIndex] ausführt:

</p>

<pre><b>Funktion</b> partition(Liste, links, rechts, pivotIndex)

pivotWert := Liste[pivotIndex]

swap Liste[pivotIndex] und Liste[rechts] <i>// Pivot ans Ende verschieben</i>

speicherIndex := links

<b>für</b> i <b>von</b> links <b>bis</b> rechts-1

<b>falls</b> Liste[i] < pivotWert

swap Liste[speicherIndex] und Liste[i]

inkrementiere speicherIndex

swap Liste[rechts] und Liste[speicherIndex] <i>// Pivot an die finale Stelle verschieben</i>

<b>return</b> speicherIndex

</pre>

<p>Dies ist bekannt als das Lomuto-<a href="Partitionsschema" title="Partitionsschema">Partitionsschema</a>, das einfacher, aber weniger effizient ist als das ursprüngliche Partitionsschema von Hoare.

</p><p>In Quicksort sortieren wir beide Zweige rekursiv, was zu einer optimalen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9981ede263cbf28215d3a70bf30f55db41a6e692.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.195ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log n)}" loading="lazy"></span> Zeit führt. Bei der Auswahl wissen wir jedoch bereits, in welcher Partition sich unser gewünschtes Element befindet, da sich der Pivot in seiner endgültigen sortierten Position befindet, mit allen, die ihm in einer unsortierten Reihenfolge vorausgehen und allen, die ihm in einer unsortierten Reihenfolge folgen. Daher findet ein einziger rekursiver Aufruf das gewünschte Element in der richtigen Partition, und darauf aufbauend, entsteht der Quickselect-Algorithmus:

</p>

<pre><i>// Gibt das k-kleinste Element der Liste zurück inklusive Rechts-/Linkselement</i>

<i>// (z.B. links <= k <= rechts).</i>

<i>// Der Speicherbedarf des Datenfelds der Suche ändert sich mit jeder Rund, aber die Liste</i>

<i>// behält immer die gleiche Größe. Deswegen muss der Wert k nicht jede Runde aktualisiert werden.</i>

<b>Funktion</b> auswählen(Liste, links, rechts, k)

<b>falls</b> links = rechts <i>// falls Liste nur ein Element enthält,</i>

<b>return</b> Liste[links] <i>// return dieses Element</i>

pivotIndex  := ... <i>// Auswahl eines Pivotelements zwischen links und rechts,</i>

<i>// z.B.,</i> links + floor(rand() % (rechts - links + 1))

pivotIndex  := partition(Liste, links, rechts, pivotIndex)

<i>// Pivot in seiner endgültigen sortierten Position</i>

<b>falls</b> k = pivotIndex

<b>return</b> Liste[k]

<b>sonst falls</b> k < pivotIndex

<b>return</b> auswählen(Liste, links, pivotIndex - 1, k)

<b>sonst</b>

<b>return</b> auswählen(Liste, pivotIndex + 1, rechts, k)

</pre>

<p>Beachten Sie die Ähnlichkeit mit Quicksort: So wie der minimal-basierte Selectionsort ein Teilselectionsort ist, so ist dies eine Teilquicksort, bei der nur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log(n))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2bf87bc27d757eed469fb13535c6243b51d0e330.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.835ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log(n))}" loading="lazy"></span> seiner <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span> -Partitionen erzeugt und partitioniert wird. Dieses einfache Verfahren hat eine erwartete lineare Laufzeit und, wie Quicksort, in der Praxis eine recht gute Leistung. Es ist auch ein In-Place-Algorithmus, der nur konstanten Speicher-Overhead erfordert, wenn die <a href="Endrekursion" title="Endrekursion">Endrekursionsoptimierung</a> verfügbar ist, oder wenn die Endrekursion mit einer Schleife eliminiert wird:

</p>

<pre><b>Funktion</b> auswählen(Liste, links, rechts, k)

<b>falls</b> links = rechts

<b>return</b> Liste[links]

pivotIndex := ... <i>// Auswahl PivotIndex zwischen links und rechts</i>

pivotIndex := partition(Liste, links, rechts, pivotIndex)

<b>falls</b> k = pivotIndex

<b>return</b> Liste[k]

<b>sonst falls</b> k < pivotIndex

rechts := pivotIndex - 1

<b>sonst</b>

links := pivotIndex + 1

</pre>

<div class="mw-heading mw-heading2"><h2 id="Zeitkomplexität"><span id="Zeitkomplexit.C3.A4t"></span>Zeitkomplexität</h2></div>

<p>Wie Quicksort hat auch der Quickselect eine gute durchschnittliche Leistung, ist aber empfindlich gegenüber dem gewählten Pivot. Wenn gute Pivots gewählt werden, d. h. solche, die den Suchsatz konsequent um einen bestimmten Bruchteil verringern, dann nimmt der Suchsatz exponentiell ab und durch Induktion (oder Summierung der geometrischen Reihen) sieht man, dass die Leistung linear ist, da jeder Schritt linear ist und die Gesamtzeit eine konstante Zeit ist (abhängig davon, wie schnell sich der Suchsatz verringert). Wenn jedoch konsequent schlechte Pivots gewählt werden, wie z. B. die Verringerung um jeweils nur ein einziges Element, dann ist die Worst-Case Performance quadratisch: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></span>. Dies geschieht z. B. bei der Suche nach dem maximalen Element einer Menge, wobei das erste Element als Pivot verwendet wird und die Daten sortiert werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">C. A. R. Hoare: <cite style="font-style:italic">Algorithm 65: find</cite>. Hrsg.: Communications of the ACM. Volume 4, Issue 7, Juli 1961, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>321–322</span> (<a rel="nofollow" class="external text" href="https://dl.acm.org/citation.cfm?doid=366622.366647">acm.org</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Quickselect&rft.au=C.+A.+R.+Hoare&rft.btitle=Algorithm+65%3A+find&rft.date=1961-07&rft.genre=book&rft.issue=Issue+7&rft.pages=321-322&rft.volume=Volume+4" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-01-03" href="https://de.wikipedia.org/wiki/?title=Quickselect&oldid=240804679">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>